﻿using System;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using System.Runtime.ConstrainedExecution;

public static class FixedMath
{
	/// Newton 法 1
	public static ulong Sqrt (ulong x)
	{
		if (x == 0) return 0;

		ulong org = x;
		ulong x1 = x - 1;
		int s = 1;
		ulong g0,g1;

		// 初值设定  通常将初始值设为1，但是只有1的开方才会是1，通过预处理找到更精确地初始值a[n]
		// 此处理能大幅度减少迭代次数 最多迭代4次即可

		if (x1 > 2147483646) 	{ s += 16; x1 >>= 32;}
		if (x1 > 65535) 		{ s += 8; x1 >>= 16;}
		if (x1 > 255)   		{ s += 4; x1 >>= 8;}
		if (x1 > 15)    		{ s += 2; x1 >>= 4;}
		if (x1 > 3)    			{ s += 1; x1 >>= 2;}

		//迭代
		g0 = (ulong)1 << s;
		g1 = (g0 + (x >> s)) >> 1;
		while(g1 < g0)
		{
			g0 = g1;
			//UnityEngine.Debug.Log("g0: " + g0);
			g1 = (g0 + x/g0) >> 1;
		}
		return g0;
	}

	/// 小数位被截断，不会四舍五入
	public static FixedPoint Sqrt (FixedPoint v)
	{
		return new FixedPoint((long) (FixedMath.Sqrt((ulong)v.rawValue) * FixedPoint.denominator_sqrt) );
	}

	// 定点数 自然对数
	public static readonly FixedPoint E = new FixedPoint(27183);
	// 定点数 圆周率
	public static readonly FixedPoint PI = new FixedPoint(31416);
	// 定点数 圆周率
	public static readonly FixedPoint PI_Two = new FixedPoint(62832);
	// 定点数 半圆周率
	public static readonly FixedPoint PI_Half = new FixedPoint(15708);

	//
	// Static Methods
	//
	public static short Abs (short value)
	{
		if (value == -32768) {
			throw new OverflowException ("Value is too small.");
		}
		return (value >= 0) ? value : (short)(-value);
	}

	public static sbyte Abs (sbyte value)
	{
		if ((int)value == -128) {
			throw new OverflowException ("Value is too small.");
		}
		return (sbyte)(((int)value >= 0) ? ((int)value) : (-(sbyte)((int)value)));
	}

	public static long Abs (long value)
	{
		if (value == -9223372036854775808) {
			throw new OverflowException ("Value is too small.");
		}
		return (value >= 0) ? value : (-value);
	}

	public static FixedPoint Abs (FixedPoint value)
	{
		return value.Abs();
	}

	public static int Abs (int value)
	{
		if (value == -2147483648) {
			throw new OverflowException ("Value is too small.");
		}
		return (value >= 0) ? value : (-value);
	}

//	public static decimal Abs (decimal value)
//	{
//		return (!(value < 0)) ? value : (-value);
//	}
//
//	public static double Abs (double value)
//	{
//		return (value >= 0) ? value : (-value);
//	}
//
//	public static float Abs (float value)
//	{
//		return (value >= 0) ? value : (-value);
//	}

	public static long BigMul (int a, int b)
	{
		return (long)a * (long)b;
	}

//	public static double Ceiling (double a)
//	{
//		double num = Math.Floor (a);
//		if (num != a) {
//			num += 1;
//		}
//		return num;
//	}

//	public static decimal Ceiling (decimal d)
//	{
//		decimal num = Math.Floor (d);
//		if (num != d) {
//			num = ++num;
//		}
//		return num;
//	}


	public static int DivRem (int a, int b, out int result)
	{
		result = a % b;
		return a / b;
	}

	public static long DivRem (long a, long b, out long result)
	{
		result = a % b;
		return a / b;
	}


//	public static decimal Floor (decimal d)
//	{
//		return decimal.Floor (d);
//	}
//

//	public static double IEEERemainder (double x, double y)
//	{
//		if (y == 0) {
//			return double.NaN;
//		}
//		double num = x - y * Math.Round (x / y);
//		if (num != 0) {
//			return num;
//		}
//		return (x <= 0) ? BitConverter.Int64BitsToDouble (-9223372036854775808) : 0;
//	}

//	public static double Log (double a, double newBase)
//	{
//		if (newBase == 1) {
//			return double.NaN;
//		}
//		double num = Math.Log (a) / Math.Log (newBase);
//		return (num != 0) ? num : 0;
//	}

	public static ushort Max (ushort val1, ushort val2)
	{
		return (val1 <= val2) ? val2 : val1;
	}

	[ReliabilityContract (Consistency.WillNotCorruptState, Cer.Success)]
	public static byte Max (byte val1, byte val2)
	{
		return (val1 <= val2) ? val2 : val1;
	}

//	[ReliabilityContract (Consistency.WillNotCorruptState, Cer.Success)]
//	public static decimal Max (decimal val1, decimal val2)
//	{
//		return (!(val1 > val2)) ? val2 : val1;
//	}

//	[ReliabilityContract (Consistency.WillNotCorruptState, Cer.Success)]
//	public static double Max (double val1, double val2)
//	{
//		if (double.IsNaN (val1) || double.IsNaN (val2)) {
//			return double.NaN;
//		}
//		return (val1 <= val2) ? val2 : val1;
//	}

//	[ReliabilityContract (Consistency.WillNotCorruptState, Cer.Success)]
//	public static float Max (float val1, float val2)
//	{
//		if (float.IsNaN (val1) || float.IsNaN (val2)) {
//			return float.NaN;
//		}
//		return (val1 <= val2) ? val2 : val1;
//	}

	[ReliabilityContract (Consistency.WillNotCorruptState, Cer.Success)]
	public static int Max (int val1, int val2)
	{
		return (val1 <= val2) ? val2 : val1;
	}

	[ReliabilityContract (Consistency.WillNotCorruptState, Cer.Success)]
	public static long Max (long val1, long val2)
	{
		return (val1 <= val2) ? val2 : val1;
	}

	public static sbyte Max (sbyte val1, sbyte val2)
	{
		return ((int)val1 <= (int)val2) ? val2 : val1;
	}

	[ReliabilityContract (Consistency.WillNotCorruptState, Cer.Success)]
	public static short Max (short val1, short val2)
	{
		return (val1 <= val2) ? val2 : val1;
	}

	public static uint Max (uint val1, uint val2)
	{
		return (val1 <= val2) ? val2 : val1;
	}

	public static ulong Max (ulong val1, ulong val2)
	{
		return (val1 <= val2) ? val2 : val1;
	}

	public static ushort Min (ushort val1, ushort val2)
	{
		return (val1 >= val2) ? val2 : val1;
	}

	[ReliabilityContract (Consistency.WillNotCorruptState, Cer.Success)]
	public static byte Min (byte val1, byte val2)
	{
		return (val1 >= val2) ? val2 : val1;
	}

	public static ulong Min (ulong val1, ulong val2)
	{
		return (val1 >= val2) ? val2 : val1;
	}

//	[ReliabilityContract (Consistency.WillNotCorruptState, Cer.Success)]
//	public static decimal Min (decimal val1, decimal val2)
//	{
//		return (!(val1 < val2)) ? val2 : val1;
//	}

//	[ReliabilityContract (Consistency.WillNotCorruptState, Cer.Success)]
//	public static double Min (double val1, double val2)
//	{
//		if (double.IsNaN (val1) || double.IsNaN (val2)) {
//			return double.NaN;
//		}
//		return (val1 >= val2) ? val2 : val1;
//	}

//	[ReliabilityContract (Consistency.WillNotCorruptState, Cer.Success)]
//	public static float Min (float val1, float val2)
//	{
//		if (float.IsNaN (val1) || float.IsNaN (val2)) {
//			return float.NaN;
//		}
//		return (val1 >= val2) ? val2 : val1;
//	}

	[ReliabilityContract (Consistency.WillNotCorruptState, Cer.Success)]
	public static int Min (int val1, int val2)
	{
		return val1 < val2 ? val1 : val2;
		//return (val1 >= val2) ? val2 : val1;
	}

	[ReliabilityContract (Consistency.WillNotCorruptState, Cer.Success)]
	public static long Min (long val1, long val2)
	{
		return val1 < val2 ? val1 : val2;
		//return (val1 >= val2) ? val2 : val1;
	}

	public static sbyte Min (sbyte val1, sbyte val2)
	{
		return ((int)val1 < (int)val2) ? val1 : val2;
		//return ((int)val1 >= (int)val2) ? val2 : val1;
	}

	[ReliabilityContract (Consistency.WillNotCorruptState, Cer.Success)]
	public static short Min (short val1, short val2)
	{
		return val1 < val2 ? val1 : val2;
		//return (val1 >= val2) ? val2 : val1;
	}

	public static uint Min (uint val1, uint val2)
	{
		return val1 < val2 ? val1 : val2;
		//return (val1 >= val2) ? val2 : val1;
	}


//	public static decimal Round (decimal d)
//	{
//		decimal num = decimal.Floor (d);
//		decimal d2 = d - num;
//		if ((d2 == (decimal)0.5 && (decimal)2.0 * (num / (decimal)2.0 - decimal.Floor (num / (decimal)2.0)) != (decimal)0.0) || d2 > (decimal)0.5) {
//			num = ++num;
//		}
//		return num;
//	}

//	public static decimal Round (decimal d, int decimals)
//	{
//		return decimal.Round (d, decimals);
//	}

//	public static decimal Round (decimal d, MidpointRounding mode)
//	{
//		if (mode != MidpointRounding.ToEven && mode != MidpointRounding.AwayFromZero) {
//			throw new ArgumentException ("The value '" + mode + "' is not valid for this usage of the type MidpointRounding.", "mode");
//		}
//		if (mode == MidpointRounding.ToEven) {
//			return Math.Round (d);
//		}
//		return FixedMath.RoundAwayFromZero (d);
//	}

//	public static decimal Round (decimal d, int decimals, MidpointRounding mode)
//	{
//		return decimal.Round (d, decimals, mode);
//	}


//	public static double Round (double value, MidpointRounding mode)
//	{
//		if (mode != MidpointRounding.ToEven && mode != MidpointRounding.AwayFromZero) {
//			throw new ArgumentException ("The value '" + mode + "' is not valid for this usage of the type MidpointRounding.", "mode");
//		}
//		if (mode == MidpointRounding.ToEven) {
//			return Math.Round (value);
//		}
//		if (value > 0) {
//			return Math.Floor (value + 0.5);
//		}
//		return Math.Ceiling (value - 0.5);
//	}


//	private static decimal RoundAwayFromZero (decimal d)
//	{
//		decimal num = decimal.Floor (d);
//		decimal d2 = d - num;
//		if (num >= (decimal)0 && d2 >= (decimal)0.5) {
//			num = ++num;
//		}
//		else {
//			if (num < (decimal)0 && d2 > (decimal)0.5) {
//				num = ++num;
//			}
//		}
//		return num;
//	}

//	public static int Sign (decimal value)
//	{
//		if (value > 0) {
//			return 1;
//		}
//		return (!(value == 0)) ? -1 : 0;
//	}

//	public static int Sign (double value)
//	{
//		if (double.IsNaN (value)) {
//			throw new ArithmeticException ("NAN");
//		}
//		if (value > 0) {
//			return 1;
//		}
//		return (value != 0) ? -1 : 0;
//	}

//	public static int Sign (float value)
//	{
//		if (float.IsNaN (value)) {
//			throw new ArithmeticException ("NAN");
//		}
//		if (value > 0) {
//			return 1;
//		}
//		return (value != 0) ? -1 : 0;
//	}

	public static int Sign (int value)
	{
		if (value > 0) {
			return 1;
		}
		return (value != 0) ? -1 : 0;
	}

	public static int Sign (long value)
	{
		if (value > 0) {
			return 1;
		}
		return (value != 0) ? -1 : 0;
	}

	public static int Sign (FixedPoint value)
	{
		if (value.rawValue > 0) {
			return 1;
		}
		return (value.rawValue != 0) ? -1 : 0;
	}

	public static int Sign (sbyte value)
	{
		if ((int)value > 0) {
			return 1;
		}
		return ((int)value != 0) ? -1 : 0;
	}

	public static int Sign (short value)
	{
		if (value > 0) {
			return 1;
		}
		return (value != 0) ? -1 : 0;
	}


//	public static decimal Truncate (decimal d)
//	{
//		return decimal.Truncate (d);
//	}
//
//	public static double Truncate (double d)
//	{
//		if (d > 0) {
//			return Math.Floor (d);
//		}
//		if (d < 0) {
//			return Math.Ceiling (d);
//		}
//		return d;
//	}

	// (8976 +8976 + 7854 + 2001 + 2001 = 29808) * 8 / 1024 = 232.875KB

	// 2   PI = 62832
	// 0.5 PI = 15708 = 2 * 2 * 3 * 7 * 11 * 17

	// sin
	const  int SIN_RADIAN_DELTA = 7;
	const  int SIN_ARRAY_LEN = 62832 / SIN_RADIAN_DELTA;// 2PI / delta
	const  int SIN_ARRAY_INDEX_MAX = SIN_ARRAY_LEN - 1;

	// cos
	const  int COS_RADIAN_DELTA = 7;
	const  int COS_ARRAY_LEN = 62832 / SIN_RADIAN_DELTA;// 2PI / delta
	const  int COS_ARRAY_INDEX_MAX = COS_ARRAY_LEN - 1;

	// tan 同时用于计算atan
	const  int TAN_RADIAN_DELTA = 2;
	const  int TAN_ARRAY_LEN = 15708 / TAN_RADIAN_DELTA;// 0.5PI / delta
	const  int TAN_ARRAY_INDEX_MAX = TAN_ARRAY_LEN - 1;

	// asin
	const  int ASIN_VALUE_DELTA = 10;
	const  int ASIN_ARRAY_INDEX_MAX = (int)(20000 / ASIN_VALUE_DELTA); // 2 / delta

	// acos
	const  int ACOS_VALUE_DELTA = 10;
	const  int ACOS_ARRAY_INDEX_MAX = (int)(20000 / ACOS_VALUE_DELTA); // 2 / delta

	// ===========================================================================
	//  用于定点三角函数计算
	// ===========================================================================

	public static int Clamp (int value, int min, int max)
	{
		if (value < min) value = min;
		else if (value > max) value = max;

		return value;
	}
	public static FixedPoint Clamp (FixedPoint value, FixedPoint min, FixedPoint max)
	{
		if (value < min) value = min;
		else if (value > max) value = max;

		return value;
	}

	/// 角度转弧度
	public static FixedPoint Angle2Radian (FixedPoint angle)
	{
		return angle * PI / 180;
	}
	public static FixedPoint Deg2Rad (FixedPoint angle)
	{
		return Angle2Radian(angle);
	}
	/// 弧度转角度
	public static FixedPoint Radian2Angle (FixedPoint radian)
	{
		return radian * 180 / PI;
	}
	public static FixedPoint Rad2Deg (FixedPoint radian)
	{
		return Radian2Angle(radian);
	}

	private static int GetTriangleArrayIndex (FixedPoint radian)
	{
		// 2   PI = 62832
		// 0.5 PI = 15708 = 2 * 2 * 3 * 7 * 11 * 17
		// 2   PI = 68 * 924

		// sin (0 ~ 2PI)
		radian = radian.Repeat(PI_Two);
		int index = radian.IndexOfInterval_Factor(68);
		index = Clamp(index, 0, 923);

		return index;
	}

	public static FixedPoint Sin (FixedPoint radian)
	{
		// 弧度重复范围 sin (0 ~ 2PI)
		radian = radian.Repeat(PI_Two);
		// 取索引
		int index = radian.IndexOfInterval_Factor(SIN_RADIAN_DELTA);
		// 索引限定
		index = Clamp(index, 0, SIN_ARRAY_INDEX_MAX);
		// 读表取值
		return new FixedPoint(FixedMathTable._sinArray[index]);
	}

	public static FixedPoint Cos (FixedPoint radian)
	{
		// 弧度重复范围 cos (0 ~ 2PI)
		radian = radian.Repeat(PI_Two);
		// 取索引
		int index = radian.IndexOfInterval_Factor(COS_RADIAN_DELTA);
		// 索引限定
		index = Clamp(index, 0, COS_ARRAY_INDEX_MAX);
		// 读表取值
		return new FixedPoint(FixedMathTable._cosArray[index]);
	}

	public static FixedPoint Tan (FixedPoint radian)
	{
		// 弧度重复范围 tan (-0.5PI ~ 0.5PI)
		radian = radian.Repeat(-PI_Half, PI);

		// 负值确定
		bool neg = false;
		if (radian < 0)
		{
			neg = true;
			radian = -radian;
		}

		// 取索引
		int index = radian.IndexOfInterval_Factor(TAN_RADIAN_DELTA);
		// 索引限定
		index = Clamp(index, 0, TAN_ARRAY_INDEX_MAX);

		// 读表取值
		long value = FixedMathTable._tanArray[index];

		// 负值确认
		if (neg)
		{
			value = -value;
		}

		// 返回数据
		return new FixedPoint(value);
	}

	public static FixedPoint Asin (FixedPoint value)
	{
		// 范围校验 sin value -1 ~ +1
		if (value < FixedPoint.NegativeOne || value > FixedPoint.One)
		{
			throw new System.Exception("asin值越界: " + value);
		}
		// 取索引
		int index = value.IndexOfInterval_Factor(-10000, ASIN_VALUE_DELTA);
		// 索引限定
		index = Clamp(index, 0, ASIN_ARRAY_INDEX_MAX);
		// 读表取值
		return new FixedPoint(FixedMathTable._asinArray[index]);
	}

	public static FixedPoint Acos (FixedPoint value)
	{
		// 范围校验 sin value -1 ~ +1
		if (value < FixedPoint.NegativeOne || value > FixedPoint.One)
		{
			throw new System.Exception("acos值越界: " + value);
		}
		// 取索引
		int index = value.IndexOfInterval_Factor(-10000, ACOS_VALUE_DELTA);
		// 索引限定
		index = Clamp(index, 0, ACOS_ARRAY_INDEX_MAX);
		// 读表取值
		return new FixedPoint(FixedMathTable._acosArray[index]);
	}

	public static FixedPoint Atan (FixedPoint value)
	{
		bool nav = false;// 负
		if (value < 0)
		{
			nav = true;
			value = -value;
		}

		int index = Find(value.rawValue, FixedMathTable._tanArray, 0, FixedMathTable._tanArray.Length);

		int factor = TAN_RADIAN_DELTA * index;
		if (nav)
		{
			factor = -factor;
		}
		FixedPoint radian = new FixedPoint(factor);

		return radian;
	}

	public static FixedPoint Atan2(FixedPoint y, FixedPoint x)
	{
		if (y.rawValue == 0)
		{
			if (x.rawValue >= 0)
			{
				return FixedPoint.Zero;
			}
			else
			{
				return PI;
			}
		}

		if (x.rawValue == 0)
		{
			if (y.rawValue >= 0)
			{
				return PI_Half;
			}
			else
			{
				return -PI_Half;
			}
		}

		FixedPoint atan = Atan(y / x);
		
		// 1/4象限
		if (x.rawValue > 0)
		{
			return atan;
		}
		else
		{
			// 2 象限
			if (y.rawValue > 0)
			{
				return atan + PI;
			}
			// 3 象限
			else
			{
				return atan - PI;
			}
		}
	}

	// 快速查找 区间值
    private static int Find (long value, long[] array, int index, int count)
	{
		if (count == 1)
		{
			return index;
		}
		else if (count == 2)
		{
			if (value < (array[index] + array[index + 1]) / 2)// 中间值比较
			{
				return index;
			}
			else
			{
				return index + 1;
			}
		}

		int middleRgt = index + count / 2;// 中间索引 左边
		int middleLft = middleRgt - 1;// 中间索引 右边


		if (value == array[middleLft])
		{
			return middleLft;
		}
		else if (value == array[middleRgt])
		{
			return middleRgt;
		}

		if (value < (array[middleLft] + array[middleRgt]) / 2)
		{
			return Find(value, array, index, middleRgt - index);
		}
		else
		{
			return Find(value, array, middleRgt, count - (middleRgt - index));
		}
	}
}
